package com.zrf.base.knowledge.collections;

import lombok.AllArgsConstructor;

import java.io.Serializable;
import java.util.AbstractMap;
import java.util.AbstractSet;
import java.util.Iterator;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.Objects;
import java.util.Set;
import java.util.Spliterator;
import java.util.function.BiConsumer;
import java.util.function.BiFunction;
import java.util.function.Consumer;
import java.util.function.Function;

/**
 * 自己实现hash map
 *
 * @author zhouruifeng
 *         Created by zhouruifeng on 2017/4/26.
 */
public class MyHashMap<K, V> extends AbstractMap<K, V> implements Map<K, V>, Cloneable, Serializable {
    private static final long serialVersionUID = 1451332612540189639L;
    /**
     * 默认初始化容量
     */
    private static final int DEFAULT_INITIAL_CAPACITY = 16;
    /**
     * 默认负载因子
     */
    private static final float DEFAULT_LOAD_FACTOR = 0.75f;
    /**
     * 最大的容量
     */
    private static final int MAXIMUM_CAPACITY = 1 << 30;
    /**
     * 真实存储的数组
     */
    private transient Node<K, V>[] table;
    /**
     * 键值对的集合
     */
    private transient Set<Map.Entry<K, V>> entrySet;
    /**
     * map的大小
     */
    private transient int size;
    /**
     * 负载因子
     */
    private final float loadFactor;
    /**
     * 数组的阀值
     */
    private int threshold;

    public MyHashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0) {
            throw new IllegalArgumentException("初始化的容量不能小于0,参数为" + initialCapacity);
        }
        if (initialCapacity > MAXIMUM_CAPACITY) {
            initialCapacity = MAXIMUM_CAPACITY;
        }
        if (loadFactor <= 0) {
            throw new IllegalArgumentException("负载因子不能小于0,参数为" + loadFactor);
        }
        this.loadFactor = loadFactor;
        this.threshold = tableSizeFor(initialCapacity);
    }

    public MyHashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

    public MyHashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
    }

    public MyHashMap(Map<? extends K, ? extends V> m) {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        putMapEntries(m, false);
    }

    @Override
    public void clear(){
        if(table != null && size > 0){
            for (int i = 0; i < table.length; i++) {
                table[i] = null;
            }
            size = 0;
        }
    }

    @Override
    public Set<Entry<K, V>> entrySet() {
        return entrySet == null ? entrySet = new EntrySet() : entrySet;
    }

    @Override
    public V getOrDefault(Object key, V defaultValue) {
        Node<K, V> node = getNode(key, hash(key));
        return node == null ? defaultValue : node.value;
    }

    @Override
    public void forEach(BiConsumer<? super K, ? super V> action) {
        if (table != null) {
            for (Node<K, V> node : table) {
                for (; node != null; node = node.nextNode) {
                    action.accept(node.key, node.value);
                }
            }
        }
    }

    @Override
    public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
        if (table != null) {
            for (Node<K, V> node : table) {
                for (; node != null; node = node.nextNode) {
                    node.value = function.apply(node.key, node.value);
                }
            }
        }
    }

    @Override
    public V putIfAbsent(K key, V value) {
        return putVal(hash(key), key, value, true, true);
    }

    @Override
    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }

    @Override
    public boolean remove(Object key, Object value) {
        return remove(hash(key), key, value, true) != null;
    }

    @Override
    public boolean replace(K key, V oldValue, V newValue) {
        Node<K, V> node = getNode(key, hash(key));
        if (node != null && Objects.equals(node.value, oldValue)) {
            node.value = newValue;
            afterNodeAccess(node);
            return true;
        }
        return false;
    }

    @Override
    public V replace(K key, V value) {
        Node<K, V> node = getNode(key, hash(key));
        V oldValue = null;
        if (node != null) {
            oldValue = node.value;
            node.value = value;
        }
        return oldValue;
    }

    /**
     * 如果key不存在或者value为null
     * 使用计算的值插入
     *
     * @param key
     * @param mappingFunction
     * @return
     */
    @Override
    public V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) {
        if (table == null || table.length == 0 || size > threshold) {
            reSize();
        }
        V result;
        int hash = hash(key);
        Node<K, V> node = getNode(key, hash);
        if (node == null || node.value == null) {
            V value = mappingFunction.apply(key);
            result = value;
            if (node != null) {
                node.value = value;
                afterNodeAccess(node);
            } else {
                putVal(hash, key, value, false, true);
            }
        } else {
            result = node.value;
        }
        return result;
    }

    /**
     * 如果包含该key,计算新的值,如果新值为空remove该key,否则修改value为新的value
     *
     * @param key
     * @param remappingFunction
     * @return
     */
    @Override
    public V computeIfPresent(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
        int hash = hash(key);
        Node<K, V> node = getNode(key, hash);
        if (node != null && node.value != null) {
            V newValue = remappingFunction.apply(node.key, node.value);

            if (newValue != null) {
                node.value = newValue;
                afterNodeAccess(node);
                return node.value;
            } else {
                remove(hash, key, null, false);
            }
        }
        return null;
    }

    @Override
    public V compute(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
        if (table == null || table.length == 0) {
            reSize();
        }
        int hash = hash(key);
        Node<K, V> node = getNode(key, hash);
        V oldValue = node == null ? null : node.value;
        V newValue = remappingFunction.apply(key, oldValue);
        if (node != null) {
            node.value = newValue;
            afterNodeAccess(node);
        } else {
            putVal(hash, key, newValue, false, true);
        }

        return newValue;
    }

    /**
     * 该方法会先根据key参数获取该Map中对应的value。
     * 如果获取的value为null，则直接使用传入的value覆盖原value（在这种情况下，可能会添加一组key-value）；
     * 如果获取的value不为null，则使用remappingFunction函数根据原value、新value计算一个新的结果，并用新的结果去覆盖原有的value。
     *
     * @param key
     * @param value
     * @param remappingFunction
     * @return
     */
    @Override
    public V merge(K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
        int hash = hash(key);
        Node<K, V> node = getNode(key, hash);
        V result = null;
        if (node != null) {
            if (node.value != null) {
                node.value = remappingFunction.apply(value, node.value);
                return node.value;
            } else {
                node.value = value;
            }
            afterNodeAccess(node);
        } else {
            putVal(hash, key, value, false, true);
        }
        return result;
    }

    private void putMapEntries(Map<? extends K, ? extends V> needAddMap, boolean evict) {
        int needAddMapSize = needAddMap.size();
        if (needAddMapSize <= 0) {
            return;
        }
        if (table == null) {
            //初始化
            float ft = ((float) needAddMapSize / loadFactor) + 1.0F;
            int t = (int) Math.min(ft, MAXIMUM_CAPACITY);

            if (t > threshold) {
                threshold = tableSizeFor(t);
            }
        } else if (needAddMapSize > threshold) {
            //重新计算数组大小
            reSize();
        }

        for (Map.Entry<? extends K, ? extends V> e : needAddMap.entrySet()) {
            K key = e.getKey();
            V value = e.getValue();
            putVal(hash(key), key, value, false, evict);
        }
    }

    private Node<K, V>[] reSize() {
        Node<K, V>[] oldTable = table;
        int oldCapacity = (table == null) ? 0 : table.length;

        if (oldCapacity >= MAXIMUM_CAPACITY) {
            //如果之前数组容量已经大于最大的容量,直接返回老的table
            threshold = Integer.MAX_VALUE;
            return table;
        }
        int newCapacity = reSizeCapacityAndThreshold();

        return genNewTableAndCopy(oldTable, oldCapacity, newCapacity);
    }

    /**
     * 根据新的数组的容量生成一个新的数组,并且将老的数据拷贝到新的数组中
     *
     * @param oldTable    老的数组
     * @param oldCapacity 数组之前的大小
     * @param newCapacity 新的数组大小
     * @return 生成的新的数组
     */
    private Node<K, V>[] genNewTableAndCopy(Node<K, V>[] oldTable, int oldCapacity, int newCapacity) {
        Node<K, V>[] newTab = (Node<K, V>[]) new Node[newCapacity];
        table = newTab;
        if (oldTable == null) {
            return newTab;
        }
        for (int j = 0; j < oldCapacity; ++j) {
            Node<K, V> e = oldTable[j];
            if (e == null) {
                continue;
            }
            oldTable[j] = null;
            if (e.nextNode == null) {
                //链表只有一个节点
                putNode(e);
            } else { // preserve order
                Node<K, V> next;
                do {
                    next = e.nextNode;
                    putNode(e);
                } while ((e = next) != null);
            }
        }
        return newTab;
    }

    /**
     * 添加一个新的元素到table中
     * 先根据hash计算出在数组中的index
     * 判断数组中当前位置是否有数据,如果没有数据直接设置值,并且将改节点的nextNode设为null
     * 否则使用头插法将数据插入到当前index的链表的头部
     */
    private void putNode(final Node<K, V> node) {
        int tableIndex = node.hash & (table.length - 1);

        Node<K, V> data = table[tableIndex];
        if (data == null) {
            table[tableIndex] = node;
            node.nextNode = null;
        } else {
            node.nextNode = data;
            table[tableIndex] = node;
        }
    }

    /**
     * 重新计算数组的容量和阀值
     *
     * @return 计算后新的数组的容量
     */
    private int reSizeCapacityAndThreshold() {
        int oldCapacity = (table == null) ? 0 : table.length;
        int oldThreshold = threshold;
        int newCapacity, newThreshold = 0;

        if (oldCapacity > 0) {
            if ((newCapacity = oldCapacity << 1) < MAXIMUM_CAPACITY && oldCapacity >= DEFAULT_INITIAL_CAPACITY) {
                //数组容量扩容两倍,如果老的容量大于初始默认容量,阀值也扩容两倍
                newThreshold = oldThreshold << 1; // double threshold
            }
        } else if (oldThreshold > 0) {
            //数组容量为0,阀值>0 扩容的容量为之前的阀值
            newCapacity = oldThreshold;
        } else {
            //都为0,扩容后都为默认值
            newCapacity = DEFAULT_INITIAL_CAPACITY;
            newThreshold = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        if (newThreshold == 0) {
            float ft = (float) newCapacity * loadFactor;
            newThreshold = (newCapacity < MAXIMUM_CAPACITY && ft < (float) MAXIMUM_CAPACITY ?
                    (int) ft : Integer.MAX_VALUE);
        }
        threshold = newThreshold;
        return newCapacity;
    }

    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K, V> p;
        int i;
        if (table == null || table.length == 0) {
            reSize();
        }
        int tableIndex = (table.length - 1) & hash;
        Node<K, V> data = table[tableIndex];
        V oldValue = null;
        if (data != null) {
            for (Node<K, V> node = data; node != null; node = node.nextNode) {
                if (Objects.equals(key, node.key)) {
                    oldValue = node.value;
                    if (oldValue == null || !onlyIfAbsent) {
                        node.value = value;
                    }
                    afterNodeAccess(node);
                    return oldValue;
                }
            }
        }
        Node<K, V> newNode = new Node<>(key, hash, value, data);
        table[tableIndex] = newNode;

        if (++size > threshold) {
            reSize();
        }
        afterNodeInsertion(evict);
        return null;
    }

    /**
     * 根据hash和key获取该节点,如果不存在则返回null
     *
     * @param key key
     * @return the node, or null if none
     */
    final Node<K, V> getNode(Object key, int hash) {
        if (table == null || table.length <= 0) {
            return null;
        }
        int tableIndex = hash & (table.length - 1);

        for (Node<K, V> node = table[tableIndex]; node != null; node = node.nextNode) {
            if (Objects.equals(node.key, key)) {
                return node;
            }
        }
        return null;
    }

    final Node<K, V> remove(int hash, Object key, Object value, boolean isMatchValue) {
        if (table != null && table.length > 0) {
            int tableIndex = hash & (table.length - 1);
            Node<K, V> lastNode = null;
            for (Node<K, V> node = table[tableIndex]; node != null; lastNode = node, node = node.nextNode) {
                if (Objects.equals(node.key, key) && (!isMatchValue || Objects.equals(node.value, value))) {
                    if (lastNode != null) {
                        lastNode.nextNode = node.nextNode;
                    } else if (node.nextNode != null) {
                        table[tableIndex] = node.nextNode;
                    } else {
                        table[tableIndex] = null;
                    }
                    size--;
                    afterNodeRemoval(node);
                    return node;
                }
            }
        }

        return null;
    }

    // Callbacks to allow LinkedHashMap post-actions
    void afterNodeAccess(Node<K, V> p) {
    }

    void afterNodeInsertion(boolean evict) {
    }

    void afterNodeRemoval(Node<K, V> p) {
    }

    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

    static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : n + 1;
    }

    @AllArgsConstructor
    static class Node<K, V> implements Map.Entry<K, V> {
        final K key;
        final int hash;
        V value;
        Node<K, V> nextNode;

        @Override
        public K getKey() {
            return key;
        }

        @Override
        public V getValue() {
            return value;
        }

        @Override
        public V setValue(V value) {
            V oldValue = this.value;
            this.value = value;
            return oldValue;
        }

        @Override
        public String toString() {
            return String.format(key + "=" + value);
        }

        @Override
        public int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }

        @Override
        public boolean equals(Object obj) {
            if (this == obj) {
                return true;
            }
            if (obj instanceof Map.Entry) {
                Map.Entry<K, V> entry = (Entry<K, V>) obj;
                return Objects.equals(entry.getKey(), this.getKey()) && Objects.equals(entry.getValue(), this.getValue());
            }
            return false;
        }
    }

    final class EntrySet extends AbstractSet<Entry<K, V>> {
        @Override
        public final int size() {
            return size;
        }

        @Override
        public final void clear() {
            MyHashMap.this.clear();
        }

        @Override
        public final Iterator<Entry<K, V>> iterator() {
            return new EntryIterator();
        }

        public final boolean contains(Object o) {
            if (!(o instanceof Map.Entry))
                return false;
            Map.Entry<?, ?> e = (Map.Entry<?, ?>) o;
            Object key = e.getKey();
            Node<K, V> candidate = getNode(key, hash(key));
            return candidate != null && candidate.equals(e);
        }

        public final boolean remove(Object o) {
            if (o instanceof Map.Entry) {
                Map.Entry<?, ?> e = (Map.Entry<?, ?>) o;
                Object key = e.getKey();
                Object value = e.getValue();
                return MyHashMap.this.remove(hash(key), key, value, true) != null;
            }
            return false;
        }

        public final Spliterator<Entry<K, V>> spliterator() {
            return new EntrySpliterator(MyHashMap.this, 0, -1, 0, 0);
        }

        public final void forEach(Consumer<? super Entry<K, V>> action) {
            Node<K, V>[] tab;
            if (action == null)
                throw new NullPointerException();
            if (size > 0 && (tab = table) != null) {
                for (int i = 0; i < tab.length; ++i) {
                    for (Node<K, V> e = tab[i]; e != null; e = e.nextNode)
                        action.accept(e);
                }
            }
        }
    }

    static final class EntrySpliterator<K, V>
            extends HashMapSpliterator<K, V>
            implements Spliterator<Map.Entry<K, V>> {
        EntrySpliterator(MyHashMap<K, V> m, int origin, int fence, int est,
                         int expectedModCount) {
            super(m, origin, fence, est, expectedModCount);
        }

        public EntrySpliterator<K, V> trySplit() {
            int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
            return (lo >= mid || current != null) ? null :
                    new EntrySpliterator<>(map, lo, index = mid, est >>>= 1,
                            expectedModCount);
        }

        public void forEachRemaining(Consumer<? super Map.Entry<K, V>> action) {
            int i, hi, mc;
            if (action == null)
                throw new NullPointerException();
            MyHashMap<K, V> m = map;
            Node<K, V>[] tab = m.table;
            if ((hi = fence) < 0) {
                hi = fence = (tab == null) ? 0 : tab.length;
            } else
                mc = expectedModCount;
            if (tab != null && tab.length >= hi &&
                    (i = index) >= 0 && (i < (index = hi) || current != null)) {
                Node<K, V> p = current;
                current = null;
                do {
                    if (p == null)
                        p = tab[i++];
                    else {
                        action.accept(p);
                        p = p.nextNode;
                    }
                } while (p != null || i < hi);
            }
        }

        public boolean tryAdvance(Consumer<? super Map.Entry<K, V>> action) {
            int hi;
            if (action == null)
                throw new NullPointerException();
            Node<K, V>[] tab = map.table;
            if (tab != null && tab.length >= (hi = getFence()) && index >= 0) {
                while (current != null || index < hi) {
                    if (current == null)
                        current = tab[index++];
                    else {
                        Node<K, V> e = current;
                        current = current.nextNode;
                        action.accept(e);
                        return true;
                    }
                }
            }
            return false;
        }

        public int characteristics() {
            return (fence < 0 || est == map.size ? Spliterator.SIZED : 0) |
                    Spliterator.DISTINCT;
        }
    }

    static class HashMapSpliterator<K, V> {
        final MyHashMap<K, V> map;
        Node<K, V> current;          // current node
        int index;                  // current index, modified on advance/split
        int fence;                  // one past last index
        int est;                    // size estimate
        int expectedModCount;       // for comodification checks

        HashMapSpliterator(MyHashMap<K, V> m, int origin,
                           int fence, int est,
                           int expectedModCount) {
            this.map = m;
            this.index = origin;
            this.fence = fence;
            this.est = est;
            this.expectedModCount = expectedModCount;
        }

        final int getFence() { // initialize fence and size on first use
            int hi;
            if ((hi = fence) < 0) {
                MyHashMap<K, V> m = map;
                est = m.size;
                Node<K, V>[] tab = m.table;
                hi = fence = (tab == null) ? 0 : tab.length;
            }
            return hi;
        }

        public final long estimateSize() {
            getFence(); // force init
            return (long) est;
        }
    }


    final class EntryIterator extends HashIterator
            implements Iterator<Map.Entry<K, V>> {

        public final Map.Entry<K, V> next() {
            return nextNode();
        }
    }

    abstract class HashIterator {
        Node<K, V> next;        // next entry to return
        Node<K, V> current;     // current entry
        int index;             // current slot

        HashIterator() {
            Node<K, V>[] t = table;
            current = next = null;
            index = 0;
            if (t != null && size > 0) { // advance to first entry
                do {
                } while (index < t.length && (next = t[index++]) == null);
            }
        }

        public final boolean hasNext() {
            return next != null;
        }

        final Node<K, V> nextNode() {
            Node<K, V>[] t;
            Node<K, V> e = next;
            if (e == null)
                throw new NoSuchElementException();
            if ((next = (current = e).nextNode) == null && (t = table) != null) {
                do {
                } while (index < t.length && (next = t[index++]) == null);
            }
            return e;
        }

        public final void remove() {
            Node<K, V> p = current;
            if (p == null)
                throw new IllegalStateException();
            current = null;
            K key = p.key;
            MyHashMap.this.remove(hash(key), key, null, false);
        }
    }
}
